home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / poly3d-h / prepdata.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-12  |  33.7 KB  |  825 lines
  1. /*****************************************************************************
  2. *   Routines to    prepare objects according to view file matrix:             *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 1.0, Jan. 1989   *
  5. *****************************************************************************/
  6.  
  7. #include <math.h>
  8. #include <stdio.h>
  9. #include "program.h"
  10. #include "genmat.h"
  11.  
  12. /* #define DEBUG1                  Print edge/hash table content. */
  13.  
  14. #define SAME_VERTEX(V1, V2)    (APX_EQ(V1 -> Coord[0], V2 -> Coord[0]) && \
  15.                  APX_EQ(V1 -> Coord[1], V2 -> Coord[1]) && \
  16.                  APX_EQ(V1 -> Coord[2], V2 -> Coord[2]))
  17.  
  18. #ifdef DEBUG1
  19. static void PrintEdgeContent(EdgeStruct *PEdge);
  20. static void DrawEdgeHashTable(void);
  21. static void DrawEdge(EdgeStruct *PEdge);
  22. #endif /* DEBUG1 */
  23.  
  24. static int MinYLevel, MaxYLevel, CrntYLevel, PrintYLevel;
  25.  
  26. static void PrepareOneObject(IPObjectStruct *PObject);
  27. static int PrepareOnePolygon(IPPolygonStruct *PPolygon, int IsPolygon);
  28. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon);
  29. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversePoly);
  30. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon, int IsPolygon);
  31. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge);
  32. static void IntersectAllEdges(void);
  33. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge);
  34. static int IntersectEdgeList(EdgeStruct *PEdge,
  35.                  EdgeStruct *PEList,
  36.                  int TestYMin);
  37. static int IntersectEdgeEdge(EdgeStruct *PEdge1,
  38.                  EdgeStruct *PEdge2,
  39.                  EdgeStruct **PEdgeNew1,
  40.                  EdgeStruct **PEdgeNew2);
  41. static void PrintPolyContent(IPPolygonStruct *PPoly);
  42.  
  43. /*****************************************************************************
  44. * DESCRIPTION:                                                               M
  45. * Routine to prepare the given object for hidden surface analysis.         M
  46. *   If NumOfObjects == 0 then all the objects defined by the data sturcture  M
  47. * are drawn.                                     M
  48. *   If GlblNumEdge != 0 then only GlblNumEdge first edges of each polygons   M
  49. * are tested for visibility (usefull in case in input polygons has known     M
  50. * repetition edges sequence which is redundent).                 M
  51. *                                                                            *
  52. * PARAMETERS:                                                                M
  53. *   PObjects:     To prepare for hidden surface analysis.                    M
  54. *                                                                            *
  55. * RETURN VALUE:                                                              M
  56. *   void                                                                     M
  57. *                                                                            *
  58. * KEYWORDS:                                                                  M
  59. *   PrepareViewData                                                          M
  60. *****************************************************************************/
  61. void PrepareViewData(IPObjectStruct *PObjects)
  62. {
  63.     int    i;
  64.  
  65.     IritCPUTime(TRUE);
  66.  
  67.     for    (i = 0; i < EDGE_HASH_TABLE_SIZE; i++)
  68.     EdgeHashTable[i] = NULL;
  69.     for    (i = 0; i < POLY_HASH_TABLE_SIZE; i++)
  70.     PolyHashTable[i] = NULL;
  71.  
  72.     if (!GlblQuiet)
  73.     fprintf(stderr, "\nPass 2, Edges =      ");
  74.  
  75.     while (PObjects) {
  76.     if (IP_IS_POLY_OBJ(PObjects))
  77.         PrepareOneObject(PObjects);
  78.     PObjects = PObjects -> Pnext;
  79.     }
  80.  
  81.     if (!GlblQuiet)
  82.     fprintf(stderr, ",  %6.2f seconds.", IritCPUTime(FALSE));
  83.  
  84.     IntersectAllEdges();       /* Break edges to visibily uniform sub-edges. */
  85. }
  86.  
  87. /*****************************************************************************
  88. * DESCRIPTION:                                                               *
  89. * Routine to prepare one object PObject for hidden surface analysis.         *
  90. *                                                                            *
  91. * PARAMETERS:                                                                *
  92. *   PObject:    Object to prepare for freeform analysis.                     *
  93. *                                                                            *
  94. * RETURN VALUE:                                                              *
  95. *   void                                                                     *
  96. *****************************************************************************/
  97. static void PrepareOneObject(IPObjectStruct *PObject)
  98. {
  99.     int Level;
  100.     IPPolygonStruct *Ptemp,
  101.     *PList = PObject -> U.Pl;
  102.  
  103.     while (PList) {
  104.     Ptemp = PList -> Pnext;
  105.  
  106.     if (!IritPrsrIsConvexPolygon(PList)) {
  107.         static int Printed = FALSE;
  108.  
  109.         if (!Printed) {
  110.         fprintf(stderr,
  111.             "\nWARNING: Non convex polygon(s) might be in data (see CONVEX in IRIT),\n\t\t\t\toutput can be wrong as the result!\n     ");
  112.         Printed = TRUE;
  113.         }
  114.     }
  115.  
  116.     if (PrepareOnePolygon(PList, IP_IS_POLYGON_OBJ(PObject))) {
  117.         /* And add polygon into polygon hash table sorted by Ymin: */
  118.         Level = (int) ((PList -> BBox[0][1] + 1.0) * POLY_HASH_TABLE_SIZE2);
  119.         Level = BOUND(Level, 0, POLY_HASH_TABLE_SIZE1); /* Be 100% safe. */
  120.         PList -> Pnext = PolyHashTable[Level];
  121.         PolyHashTable[Level] = PList;   /* Concat it to poly hash table. */
  122.     }
  123.  
  124.     PList =    Ptemp;
  125.     }
  126. }
  127.  
  128. /*****************************************************************************
  129. * DESCRIPTION:                                                               *
  130. * Routine to prepare one poly PPolygon.                         *
  131. *   Returns TRUE iff this object is a valid POLYGON (not a POLYLINE!).         *
  132. *                                         *
  133. * PARAMETERS:                                                                *
  134. *   PPolygon:     Poly to prepare for hideden surface analysis.              *
  135. *   IsPolygon:    TRUE if polygon, FALSE otherwise (polyline etc.).          *
  136. *                                                                            *
  137. * RETURN VALUE:                                                              *
  138. *   int:          TRUE if successful, FALSE otherwise.                       *
  139. *****************************************************************************/
  140. static int PrepareOnePolygon(IPPolygonStruct *PPolygon, int IsPolygon)
  141. {
  142.     int    i, Reverse;
  143.     RealType CpCoord[3];
  144.     IPVertexStruct
  145.     *PList = PPolygon -> PVertex;
  146.  
  147.     /* Make a circluar polygon list inlt a linear list by breaking the end.  */
  148.     while (PList != NULL && PList -> Pnext != PPolygon -> PVertex)
  149.     PList = PList -> Pnext;
  150.     if (PList)
  151.     PList -> Pnext = NULL;
  152.     PList = PPolygon -> PVertex;
  153.  
  154.     while (PList) {
  155.     /* Convert the coordinate to screen space (in RealType pres.). */
  156.     MatMultVecby4by4(CpCoord, PList -> Coord, GlblViewMat);
  157.     for (i = 0; i < 3; i++)
  158.         PList -> Coord[i] = CpCoord[i];
  159.  
  160.     PList =    PList -> Pnext;
  161.     }
  162.     if (IsPolygon) {
  163.     /* Find plane equation of poly, and let know if need to reverse. */
  164.     if (!UpdateEqnPolygon(PPolygon, &Reverse))
  165.         return FALSE;
  166.     UpdateBBoxPolygon(PPolygon);/* Find X, Y extrem in screen space. */
  167.     GenEdgesFromPoly(PPolygon, TRUE);      /* Generate all its edges. */
  168.     if (Reverse)
  169.             IritPrsrReverseVrtxList(PPolygon);
  170.     return TRUE;
  171.     }
  172.     else {
  173.     GenEdgesFromPoly(PPolygon, FALSE);      /* Generate all its edges. */
  174.     return FALSE;
  175.     }
  176. }
  177.  
  178. /*****************************************************************************
  179. * DESCRIPTION:                                                               *
  180. * Routine to update polygon boundary box in screen space.             *
  181. *                                                                            *
  182. * PARAMETERS:                                                                *
  183. *   PPolygon:     To update bounding box for, in palce.                      *
  184. *                                                                            *
  185. * RETURN VALUE:                                                              *
  186. *   void                                                                     *
  187. *****************************************************************************/
  188. static void UpdateBBoxPolygon(IPPolygonStruct *PPolygon)
  189. {
  190.     RealType *Coord, Xmin, Xmax, Ymin, Ymax; /* Bounding box of the polygon. */
  191.     IPVertexStruct
  192.     *PList = PPolygon -> PVertex;
  193.  
  194.     Xmin = Xmax    = PList -> Coord[0];
  195.     Ymin = Ymax    = PList    -> Coord[1];
  196.     PList = PList -> Pnext;
  197.     while (PList) {
  198.     Coord = PList -> Coord;
  199.     if (Coord[0] > Xmax)
  200.         Xmax = Coord[0];
  201.     if (Coord[0] < Xmin)
  202.         Xmin = Coord[0];
  203.     if (Coord[1] > Ymax)
  204.         Ymax = Coord[1];
  205.     if (Coord[1] < Ymin)
  206.         Ymin = Coord[1];
  207.     PList =    PList -> Pnext;
  208.     }
  209.     PPolygon ->    BBox[0][0] = Xmin;
  210.     PPolygon -> BBox[1][0] = Xmax;
  211.     PPolygon ->    BBox[0][1] = Ymin;
  212.     PPolygon -> BBox[1][1] = Ymax;
  213. }
  214.  
  215. /*****************************************************************************
  216. * DESCRIPTION:                                                               *
  217. * Routine to update plane equation of the given    polygon.             *
  218. *   It is assumed that at least 3 points in polygon exists. The tuple that   *
  219. * has the largest vector length is selected maximum accuracy.             *
  220. *   We IGNORE PLANE if was in data file.                     *
  221. *   In addition, a test is made if all vertices are ordered such that the    *
  222. * cross product of each 3 consecutive vertices (projected onto Z=0 plane)    *
  223. * is allways positive. The polygon must be convex, so result might be either *
  224. * all positive or all negative.                             *
  225. *   In the later case the order of the plane equation is reversed.         *
  226. *                                                                            *
  227. * PARAMETERS:                                                                *
  228. *   PPolygon:       Polygon to update plane for, and possibly reverse.       *
  229. *   ReversedPoly:   TRUE if plane equation was reversed.                     *
  230. *                                                                            *
  231. * RETURN VALUE:                                                              *
  232. *   int:            TRUE if successful, FALSE otherwise.                     *
  233. *****************************************************************************/
  234. static int UpdateEqnPolygon(IPPolygonStruct *PPolygon, int *ReversedPoly)
  235. {
  236.     static int
  237.     PolygonCount = 0;
  238.     int    i;
  239.     RealType V1[3], V2[3], *Coord, *CoordNext, *CoordNextNext,
  240.     Plane[3], Len, MaxPlane[3],
  241.     MaxLen = 0.0;
  242.     IPVertexStruct
  243.     *PList = PPolygon -> PVertex;
  244.  
  245.     PolygonCount++;
  246.  
  247.     *ReversedPoly = FALSE;
  248.  
  249.     do {    /* Search for 3 consequtive non-colinear point from polygon: */
  250.     Coord = PList -> Coord;
  251.     CoordNext = PList -> Pnext -> Coord;
  252.     CoordNextNext = PList -> Pnext -> Pnext -> Coord;
  253.     for (i = 0; i < 3; i++) {   /* Prepare two vectors on polygon plane. */
  254.         V1[i] = Coord[i] - CoordNext[i];
  255.         V2[i] = CoordNext[i] - CoordNextNext[i];
  256.     }
  257.  
  258.     /* Find plane normal by a cross product of the two vectors on plane: */
  259.     Plane[0] = V1[1] * V2[2] - V1[2] * V2[1];
  260.     Plane[1] = V1[2] * V2[0] - V1[0] * V2[2];
  261.     Plane[2] = V1[0] * V2[1] - V1[1] * V2[0];
  262.  
  263.     /* Find vector Len. - we are looking for the biggest: */
  264.     Len = sqrt(SQR(Plane[0]) + SQR(Plane[1]) + SQR(Plane[2]));
  265.     if (Len > MaxLen) {
  266.         for (i = 0; i < 3; i++)
  267.         MaxPlane[i] = Plane[i];
  268.         MaxLen = Len;
  269.     }
  270.     PList = PList -> Pnext;                  /* Try next tuple. */
  271.     } while (PList -> Pnext -> Pnext != NULL);
  272.  
  273.     if (ABS(MaxLen) < SQR(EPSILON)) { /* Fail to find 3 non-colinear points. */
  274.     if (GlblMore) {
  275.         fprintf(stderr,
  276.             "\nError: Invalid polygon (%d) found in file (zero edge length/colinear vertices):\n",
  277.         PolygonCount);
  278.         PrintPolyContent(PPolygon);
  279.     }
  280.     return FALSE;
  281.     }
  282.  
  283.     for (i = 0; i < 3; i++)
  284.     PPolygon -> Plane[i] = MaxPlane[i] / MaxLen;
  285.  
  286.     /* Make sure the Z component of the    plane is positive: */
  287.     if (PPolygon -> Plane[2] < 0.0) {
  288.     for (i = 0; i < 3; i++)
  289.         PPolygon -> Plane[i] = (-PPolygon -> Plane[i]);
  290.     *ReversedPoly = TRUE;
  291.     }
  292.     else
  293.         if (GlblBackFacing)
  294.         return FALSE;
  295.  
  296.     PPolygon ->    Plane[3] =
  297.     (- Coord[0] * PPolygon -> Plane[0]
  298.      - Coord[1] * PPolygon -> Plane[1]
  299.      - Coord[2] * PPolygon -> Plane[2]);
  300.  
  301.     return TRUE;
  302. }
  303.  
  304. /*****************************************************************************
  305. * DESCRIPTION:                                                               *
  306. * Routine to generate all the edges from the given polygon in screen space.  *
  307. *   Edges are inserted to an edge hash table of EDGE_HASH_TABLE_SIZE         *
  308. * entries.                                     *
  309. *   If global variable GlblNumEdge != 0 then only the first PGlblNumEdge     *
  310. * edges are generated.                                 *
  311. *   If edge is INTERNAL it is marked as so.                     *
  312. *   If this is polyline, the last edge is NOT generated.             *
  313. *                                                                            *
  314. * PARAMETERS:                                                                *
  315. *   PPolygon:    To generateedge from.                                       *
  316. *   IsPolygon:   TRUE for polygon, FALSE otherwise (polyline etc.).          *
  317. *                                                                            *
  318. * RETURN VALUE:                                                              *
  319. *   void                                                                     *
  320. *****************************************************************************/
  321. static void GenEdgesFromPoly(IPPolygonStruct *PPolygon, int IsPolygon)
  322. {
  323.     int    CountEdges = GlblNumEdge;
  324.     EdgeStruct *PEdge;
  325.     IPVertexStruct
  326.     *PList = PPolygon -> PVertex;
  327.  
  328.     if (!PList || !PList -> Pnext)
  329.     return;                     /* If less than 2 vertices. */
  330.  
  331.     while (PList -> Pnext) {
  332.     PEdge =    (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  333.     PEdge -> Vertex[0] = PList;
  334.     PEdge -> Vertex[1] = PList -> Pnext;
  335.     PEdge -> Internal = IP_IS_INTERNAL_VRTX(PList);
  336.     PEdge -> Pnext = NULL;
  337.     InsertEdgeToHashTbl1(PEdge);
  338.  
  339.     if (!--CountEdges)
  340.         return;
  341.  
  342.     PList =    PList -> Pnext;
  343.     }
  344.     /* Close the contour to first vertex in list (if not polyline): */
  345.     if (IsPolygon) {
  346.     PEdge = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  347.     PEdge -> Vertex[0] = PList;
  348.     PEdge -> Vertex[1] = PPolygon -> PVertex;
  349.     PEdge -> Internal = IP_IS_INTERNAL_VRTX(PList);
  350.     PEdge -> Pnext = NULL;
  351.     InsertEdgeToHashTbl1(PEdge);
  352.     }
  353. }
  354.  
  355. /*****************************************************************************
  356. * DESCRIPTION:                                                               *
  357. * Routine to insert new    edge to    edge hash table    structure sorted (hashed) by *
  358. * the edge Y min value.                                 *
  359. *   The edge is tested for duplicated entry (if interior edge it is entered  *
  360. * twice from its two adjacent polygons).                     *
  361. *   The edge is updated such that Ymin will be Vertex[0], Ymax Vertex[1].    *
  362. *                                                                            *
  363. * PARAMETERS:                                                                *
  364. *   PEdge:      Edge to insert into hash table.                              *
  365. *                                                                            *
  366. * RETURN VALUE:                                                              *
  367. *   void                                                                     *
  368. *****************************************************************************/
  369. static void InsertEdgeToHashTbl1(EdgeStruct *PEdge)
  370. {
  371.     int    Level;
  372.     RealType Xmin, Xmax, Ymin, Ymax;
  373.     IPVertexStruct *PVertex;
  374.     EdgeStruct *PEtemp;
  375.  
  376.     if (PEdge -> Vertex[0] -> Coord[1] > PEdge -> Vertex[1] -> Coord[1]) {
  377.     PVertex    = PEdge    -> Vertex[0];
  378.     PEdge -> Vertex[0] = PEdge -> Vertex[1];
  379.     PEdge -> Vertex[1] = PVertex;
  380.     }
  381.     Xmin = MIN(PEdge -> Vertex[0] -> Coord[0],
  382.            PEdge -> Vertex[1] -> Coord[0]);
  383.     Xmax = MAX(PEdge -> Vertex[0] -> Coord[0],
  384.            PEdge -> Vertex[1] -> Coord[0]);
  385.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  386.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  387.  
  388.     if (GlblClipScreen && ((Ymin > 1.0) || (Ymax < -1.0) ||
  389.                (Xmin > 1.0) || (Xmax < -1.0)))
  390.     IritFree((VoidPtr) PEdge);               /* Out of screen. */
  391.     else {
  392.     /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  393.     Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  394.     Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);     /* To be 100% safe. */
  395.  
  396.     /* Look    for duplicate entry - it must have the same two    vertices: */
  397.     PEtemp = EdgeHashTable[Level];
  398.     while (PEtemp) {
  399.         /* Test to see if same edge    by comparing vertices pointers.    */
  400.         if ((SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[0]) &&
  401.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[1])) ||
  402.         (SAME_VERTEX(PEdge -> Vertex[0], PEtemp -> Vertex[1]) &&
  403.          SAME_VERTEX(PEdge -> Vertex[1], PEtemp -> Vertex[0]))) {
  404.         IritFree((VoidPtr) PEdge);
  405.         return;                    /* Ignore new entry! */
  406.         }
  407.         PEtemp = PEtemp -> Pnext;
  408.     }
  409.  
  410.     if (!GlblQuiet)
  411.         fprintf(stderr, "\b\b\b\b\b%5d", ++EdgeCount);
  412.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  413.     EdgeHashTable[Level] = PEdge;
  414.     }
  415. }
  416.  
  417. /*****************************************************************************
  418. * DESCRIPTION:                                                               *
  419. * Routine to collect all edges in hash table into one big list and intersect *
  420. * them beween themselves.                              *
  421. *   The resulting edges are inserted back into the hash table.             *
  422. *                                                                            *
  423. * PARAMETERS:                                                                *
  424. *   None                                                                     *
  425. *                                                                            *
  426. * RETURN VALUE:                                                              *
  427. *   void                                                                     *
  428. *****************************************************************************/
  429. static void IntersectAllEdges(void)
  430. {
  431.     RealType Ymin;
  432.     int    i, Level;
  433.     EdgeStruct *PEtemp,
  434.     *PEmain = NULL;
  435.  
  436.     IritCPUTime(TRUE);
  437.  
  438.     EdgeCount =    0;
  439.     MinYLevel =    EDGE_HASH_TABLE_SIZE; /* Set "clip" levels in table entries. */
  440.     MaxYLevel =    0;
  441.  
  442.     /* Clear the hash table and    collect    all edges into one big list: */
  443.     for    (i = EDGE_HASH_TABLE_SIZE1; i >= 0; i--)
  444.     if ((PEtemp = EdgeHashTable[i]) != NULL) {
  445.         while (PEtemp -> Pnext) PEtemp = PEtemp -> Pnext;
  446.         PEtemp -> Pnext = PEmain;
  447.         PEmain = EdgeHashTable[i];
  448.         EdgeHashTable[i] = NULL;
  449.         if (i > MaxYLevel)
  450.         MaxYLevel = i;
  451.         if (i < MinYLevel)
  452.         MinYLevel = i;
  453.     }
  454.  
  455.     PrintYLevel    = CrntYLevel = 0;     /* Have to start from some place... */
  456.     if (!GlblQuiet)
  457.     fprintf(stderr, "\nPass 3, Level [%5d] =      ", MaxYLevel);
  458.  
  459.     while (PEmain) { /* Insert back after intersecting with all other edges. */
  460.     PEtemp = PEmain    -> Pnext;      /* As PEmain->Pnext might be changed. */
  461.     InsertEdgeToHashTbl2(PEmain);
  462.     PEmain = PEtemp;
  463.  
  464.     /* Now test to see if we can update current y level: */
  465.     if (CrntYLevel < MaxYLevel) {
  466.         Ymin = MIN(PEmain -> Vertex[0] -> Coord[1],
  467.                PEmain -> Vertex[1] -> Coord[1]);
  468.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  469.         Level = (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  470.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1); /* Be 100% safe. */
  471.         if (Level > CrntYLevel)
  472.         CrntYLevel = Level;
  473.     }
  474.     }
  475.     if (!GlblQuiet)
  476.     fprintf(stderr, ",  %6.2f seconds.", IritCPUTime(FALSE));
  477. }
  478.  
  479. /*****************************************************************************
  480. * DESCRIPTION:                                                               *
  481. * Routine to insert old    edge to    edge hash table    structure sorted (hashed) by *
  482. * the edge Y min value.    The edge is tested for intersections with other         *
  483. * edges    allready in structure and both edges are broken    if found one.         *
  484. *                                                                            *
  485. * PARAMETERS:                                                                *
  486. *   PEdge:     To back insert after intersection testing.                    *
  487. *                                                                            *
  488. * RETURN VALUE:                                                              *
  489. *   void                                                                     *
  490. *****************************************************************************/
  491. static void InsertEdgeToHashTbl2(EdgeStruct *PEdge)
  492. {
  493.     int    i, Level, UpperLevel,
  494.     FoundIntersection = FALSE;
  495.     RealType Ymin, Ymax;
  496.     EdgeStruct *PEtemp;
  497.  
  498.     Ymin = PEdge -> Vertex[0] -> Coord[1];
  499.     Ymax = PEdge -> Vertex[1] -> Coord[1];
  500.  
  501.     /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  502.     Level = (int) ((Ymin + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  503.     Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);      /* To be 100% safe. */
  504.     UpperLevel = 1 + (int) ((Ymax + 1.0) * EDGE_HASH_TABLE_SIZE2);
  505.     UpperLevel = BOUND(UpperLevel, 0, EDGE_HASH_TABLE_SIZE1);
  506.  
  507.     if (CrntYLevel > PrintYLevel) {
  508.     PrintYLevel = CrntYLevel;
  509.     if (!GlblQuiet)
  510.         fprintf(stderr, "\b\b\b\b\b%5d", PrintYLevel);
  511.     }
  512.  
  513.     /* Test for    intersections while we find intersections... */
  514.     for    (i=MinYLevel; i<=UpperLevel; i++)
  515.     if (EdgeHashTable[i])
  516.          if ((FoundIntersection =
  517.           IntersectEdgeList(PEdge, EdgeHashTable[i],
  518.                     i == MinYLevel)) != 0)
  519.         break;
  520.  
  521.     if (FoundIntersection) {       /* Call recursively with the edge pieces: */
  522.     while (PEdge) {
  523.         PEtemp = PEdge -> Pnext;  /* As Pedge->Pnext might point to new. */
  524.         InsertEdgeToHashTbl2(PEdge);   /* Place after the recursive ins. */
  525.         PEdge = PEtemp;
  526.     }
  527.     }
  528.     else {              /* Its a single edge - insert it in its place: */
  529.     EdgeCount++;
  530.     PEdge -> Pnext = EdgeHashTable[Level];         /* Concat to main list. */
  531.     EdgeHashTable[Level] = PEdge;
  532.     }
  533. }
  534.  
  535. /*****************************************************************************
  536. * DESCRIPTION:                                                               *
  537. * Routine to scan all edges in list and    intersect everything against         *
  538. * the given edge. Intersected edges are    broken into two.             *
  539. *   The broken edge is updated into a list of teo edges.             *
  540. *   This routine returns TRUE after the first intersection found, no test is *
  541. * made for ALL intersections if    more than one exists.                 *
  542. *   A test is made if MinYLevel can be updated if TestYMin == TRUE.         *
  543. *                                                                            *
  544. * PARAMETERS:                                                                *
  545. *   PEdge:      Edge to examine for intersection.                            *
  546. *   PEList:     List of edges to examine for intersectiong with PEdge.       *
  547. *   TestYMin:   Index Y level.                                               *
  548. *                                                                            *
  549. * RETURN VALUE:                                                              *
  550. *   int:        TRUE if found intersection, FALSE otherwise.                 *
  551. *****************************************************************************/
  552. static int IntersectEdgeList(EdgeStruct *PEdge,
  553.                  EdgeStruct *PEList,
  554.                  int TestYMin)
  555. {
  556.     int    Level,
  557.     UpdateYMin = TRUE;
  558.     RealType Ymin, Ymax;
  559.     EdgeStruct *PEdgeNew, *PEListNew;
  560.  
  561.     if (!PEdge || !PEList)
  562.     return FALSE;                       /* NULL entry - quit. */
  563.  
  564.     while (PEList) {
  565.     if (IntersectEdgeEdge(PEdge, PEList, &PEdgeNew,    &PEListNew)) {
  566.         PEdge -> Pnext = PEdgeNew;
  567.         /* PEListNew can be    inserted to the    hash table with    no check as  */
  568.         /* it cannot intersect anything - it is part of checked edge!    */
  569.         if (PEListNew) {
  570.         Ymin = PEListNew -> Vertex[0] -> Coord[1];
  571.         /* Normalize [-1..1] to    [0..EDGE_HASH_TABLE_SIZE]: */
  572.         Level =    (int) ((Ymin + 1.0) * EDGE_HASH_TABLE_SIZE2);
  573.         Level =    BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  574.         EdgeCount++;
  575.         PEListNew -> Pnext = EdgeHashTable[Level];
  576.         EdgeHashTable[Level] = PEListNew;
  577.         }
  578.         return TRUE;
  579.     }
  580.     if (TestYMin &&    UpdateYMin) {
  581.         Ymax = PEList -> Vertex[1] -> Coord[1];
  582.         /* Normalize [-1..1] to [0..EDGE_HASH_TABLE_SIZE]: */
  583.         Level = (int) ((Ymax + 1.0)    * EDGE_HASH_TABLE_SIZE2);
  584.         Level = BOUND(Level, 0, EDGE_HASH_TABLE_SIZE1);
  585.         if (Level >= CrntYLevel)
  586.         UpdateYMin = FALSE;
  587.     }
  588.     PEList = PEList    -> Pnext;
  589.     }
  590.     if (TestYMin && UpdateYMin)            /* No need to test any more. */
  591.     do
  592.         MinYLevel++;
  593.     while (MinYLevel < CrntYLevel && !EdgeHashTable[MinYLevel]);
  594.  
  595.     return FALSE;
  596. }
  597.  
  598. /*****************************************************************************
  599. * DESCRIPTION:                                                               *
  600. * Routine to test if two edges intersects. If they do, it brakes the bottom  *
  601. * edge into two pieces, leaving the lower part (with the same Ymin) in         *
  602. * original struct and allocates and updates new struct with upper edge part. *
  603. *   Returns TRUE if found intersection, FALSE otherwise.             *
  604. *   The intersection is tested in the XY axes (Z is ignored).             *
  605. *                                                                            *
  606. *                                                                            *
  607. * PARAMETERS:                                                                *
  608. *   PEdge1, PEdge2:  Two edge to intersect against each other.               *
  609. *   PEdgeNew1:       If PEdge1 is broken into two.                           *
  610. *   PEdgeNew2:       If PEdge2 is broken into two.                           *
  611. *                                                                            *
  612. * RETURN VALUE:                                                              *
  613. *   int:             TRUE if found intersection, FALSE otherwise.            *
  614. *****************************************************************************/
  615. static int IntersectEdgeEdge(EdgeStruct *PEdge1,
  616.                  EdgeStruct *PEdge2,
  617.                  EdgeStruct **PEdgeNew1,
  618.                  EdgeStruct **PEdgeNew2)
  619. {
  620.     int    i, OneInter1, OneInter2;
  621.     RealType Xmin1, Xmax1, Ymin1, Ymax1, Xmin2, Xmax2, Ymin2, Ymax2,
  622.       a1, b11, b12, a2, b21, b22, det, t1, t2, Z1, Z2;
  623.     /* To speed    up the intensive access    of the coordinates: */
  624.     RealType
  625.     *Crd10 = PEdge1 -> Vertex[0] -> Coord,
  626.     *Crd11 = PEdge1 -> Vertex[1] -> Coord,
  627.     *Crd20 = PEdge2 -> Vertex[0] -> Coord,
  628.     *Crd21 = PEdge2 -> Vertex[1] -> Coord;
  629.  
  630.     Xmin1 = MIN(Crd10[0], Crd11[0]);
  631.     Xmax1 = MAX(Crd10[0], Crd11[0]);
  632.     Ymin1 = Crd10[1];
  633.     Ymax1 = Crd11[1];
  634.  
  635.     Xmin2 = MIN(Crd20[0], Crd21[0]);
  636.     Xmax2 = MAX(Crd20[0], Crd21[0]);
  637.     Ymin2 = Crd20[1];
  638.     Ymax2 = Crd21[1];
  639.     if ((Xmin1 > Xmax2)    || (Xmax1 < Xmin2) ||/* Test if out of Boundary Box. */
  640.     (Ymin1 > Ymax2)    || (Ymax1 < Ymin2))
  641.     return FALSE;
  642.  
  643.     /* Let the line equations of the two edges be defined as:             */
  644.     /* L1 = p11    + t1 * (pt12 - pt11) , t1 = [0..1]                 */
  645.     /* L2 = p21    + t2 * (pt22 - pt21) , t2 = [0..1]                 */
  646.     /* at intersection point (if any) we have:                     */
  647.     /* pt11 + t1 * (pt12 - pt11) == pt21 + t2 *    (pt22 -    pt21)  for x, y         */
  648.     /* or two equations    (for x, y) with two unknown (t1, t2) to solve:         */
  649.     /* a1 = b11    * t1 + b12 * t2        from x                     */
  650.     /* a2 = b21    * t1 + b22 * t2        from y                     */
  651.     /* and we have interesection if both t1, t2    in the range [0..1]         */
  652.     a1 =  Crd10[0] - Crd20[0];
  653.     b11    = Crd10[0] - Crd11[0];
  654.     b12    = Crd21[0] - Crd20[0];
  655.     a2 =  Crd10[1] - Crd20[1];
  656.     b21    = Crd10[1] - Crd11[1];
  657.     b22    = Crd21[1] - Crd20[1];
  658.  
  659.     /* If the detereminant is zero, the    two lines are parellel - no inter. */
  660.     if (APX_EQ((det = b11 * b22 - b21 * b12), 0.0))
  661.     return FALSE;
  662.  
  663.     t1 = (a1 * b22 - a2    * b12) / det;
  664.     t2 = (b11 *    a2 - b21 * a1) / det;
  665.  
  666.     /* Test if intersection is happening in one    edge END - in that case    */
  667.     /* we break    only the second    edge into two parts.            */
  668.     OneInter1 =    ((t1 < 1.0) && (t1 > 0.0) &&
  669.          !(APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)) &&
  670.           (APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)));
  671.     OneInter2 =    ((t2 < 1.0) && (t2 > 0.0) &&
  672.          !(APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0)) &&
  673.           (APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0)));
  674.  
  675.     /* If out of 0..1 range in one of edges - no intersection: */
  676.     if ((!(OneInter1 ||    OneInter2)) &&
  677.     ((t1 >=    1.0) ||    (t1 <= 0.0) || (t2 >= 1.0) || (t2 <= 0.0) ||
  678.      APX_EQ(t1, 0.0) || APX_EQ(t1, 1.0) ||
  679.      APX_EQ(t2, 0.0) || APX_EQ(t2, 1.0))) return FALSE;
  680.  
  681.     /* If we are here, we have intersection - find the bottom edge and split */
  682.     /* it - allocated new edge struct and update to new upper (in Y) part.   */
  683.     Z1 = Crd10[2] * (1.0 - t1) + Crd11[2] * t1;
  684.     Z2 = Crd20[2] * (1.0 - t2) + Crd21[2] * t2;
  685.     if (!OneInter2 && Z1 < Z2) {
  686.     *PEdgeNew1 = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  687.     (*PEdgeNew1) -> Pnext = NULL;
  688.     (*PEdgeNew1) -> Internal = PEdge1 -> Internal;
  689.     (*PEdgeNew1) ->    Vertex[0] = IPAllocVertex(0, 0, NULL, NULL);
  690.     for (i = 0; i < 2; i++)
  691.         (*PEdgeNew1) -> Vertex[0] -> Coord[i] =
  692.         Crd10[i] * (1.0    - t1) +    Crd11[i] * t1;
  693.     (*PEdgeNew1) -> Vertex[0] -> Coord[2] = Z1;
  694.     /* Now update the second vertex    of both    PEdge1 & PEdgeNew1:       */
  695.     /* Note    we assume Vertex[0] -> Coord[1]    < Vertex[1] -> Coord[1]    as */
  696.     /* all input edges are sorted this way when entered to hash table. */
  697.     (*PEdgeNew1) ->    Vertex[1] = PEdge1 -> Vertex[1];
  698.     PEdge1 -> Vertex[1] = (*PEdgeNew1) -> Vertex[0];
  699.  
  700.     }
  701.     else
  702.     *PEdgeNew1 = NULL;
  703.  
  704.     if (!OneInter1 && Z2 < Z1) {
  705.     *PEdgeNew2 = (EdgeStruct *) IritMalloc(sizeof(EdgeStruct));
  706.     (*PEdgeNew2) -> Pnext = NULL;
  707.     (*PEdgeNew2) -> Internal = PEdge2 -> Internal;
  708.     (*PEdgeNew2) ->    Vertex[0] = IPAllocVertex(0, 0, NULL, NULL);
  709.     for (i = 0; i < 2; i++)
  710.         (*PEdgeNew2) -> Vertex[0] -> Coord[i] =
  711.         Crd20[i] * (1.0    - t2) +    Crd21[i] * t2;
  712.     (*PEdgeNew2) -> Vertex[0] -> Coord[2] = Z2;
  713.     /* Now update the second vertex    of both    PEdge2 & PEdgeNew2: */
  714.     (*PEdgeNew2) ->    Vertex[1] = PEdge2 -> Vertex[1];
  715.     PEdge2 -> Vertex[1] = (*PEdgeNew2) -> Vertex[0];
  716.     }
  717.     else
  718.     *PEdgeNew2 = NULL;
  719.  
  720.     return (*PEdgeNew1 != NULL) || (*PEdgeNew2 != NULL);
  721. }
  722.  
  723. /*****************************************************************************
  724. * DESCRIPTION:                                                               *
  725. * Routine to print the content of a given edge:                     *
  726. *                                                                            *
  727. * PARAMETERS:                                                                *
  728. *   PPoly:      To print content of.                                         *
  729. *                                                                            *
  730. * RETURN VALUE:                                                              *
  731. *   void                                                                     *
  732. *****************************************************************************/
  733. static void PrintPolyContent(IPPolygonStruct *PPoly)
  734. {
  735.     IPVertexStruct
  736.     *PList = PPoly -> PVertex;
  737.  
  738.     while (PList) {
  739.     fprintf(stderr, "   %12f %12f %12f\n",
  740.         PList -> Coord[0],
  741.         PList -> Coord[1],
  742.         PList -> Coord[2]);
  743.     PList =    PList -> Pnext;
  744.     }
  745. }
  746.  
  747. #ifdef DEBUG1
  748.  
  749. /*****************************************************************************
  750. * DESCRIPTION:                                                               *
  751. * Routine to print the content of a given edge:                     *
  752. *                                                                            *
  753. * PARAMETERS:                                                                *
  754. *   PEdge:      To print content of                                          *
  755. *                                                                            *
  756. * RETURN VALUE:                                                              *
  757. *   void                                                                     *
  758. *****************************************************************************/
  759. static void PrintEdgeContent(EdgeStruct *PEdge)
  760. {
  761.     fprintf(stderr, "   %11f %11f %11f : %11f %11f %11f\n",
  762.     PEdge -> Vertex[0] -> Coord[0],
  763.     PEdge -> Vertex[0] -> Coord[1],
  764.     PEdge -> Vertex[0] -> Coord[2],
  765.     PEdge -> Vertex[1] -> Coord[0],
  766.     PEdge -> Vertex[1] -> Coord[1],
  767.     PEdge -> Vertex[1] -> Coord[2]);
  768. }
  769.  
  770. /*****************************************************************************
  771. * DESCRIPTION:                                                               *
  772. * Routine to dump all the segments in the EdgeHashTable as IRIT data file so *
  773. * it can be displayed, to stdout.                                            *
  774. *                                                                            *
  775. * PARAMETERS:                                                                *
  776. *   None                                                                     *
  777. *                                                                            *
  778. * RETURN VALUE:                                                              *
  779. *   void                                                                     *
  780. *****************************************************************************/
  781. static void DrawEdgeHashTable(void)
  782. {
  783.     int    i;
  784.     EdgeStruct *PEtemp;
  785.  
  786.     for    (i=0; i<EDGE_HASH_TABLE_SIZE; i++) {
  787.     PEtemp = EdgeHashTable[i];
  788.     while(PEtemp) {
  789.         DrawEdge(PEtemp);
  790.         PEtemp = PEtemp -> Pnext;
  791.     }
  792.     }
  793. }
  794.  
  795. /*****************************************************************************
  796. * DESCRIPTION:                                                               *
  797. * Routine to dump one segment as IRIT data file so it can be displayed, to   *
  798. * stdout.                                                         *
  799. *                                                                            *
  800. * PARAMETERS:                                                                *
  801. *   None                                                                     *
  802. *                                                                            *
  803. * RETURN VALUE:                                                              *
  804. *   void                                                                     *
  805. *****************************************************************************/
  806. static void DrawEdge(EdgeStruct *PEdge)
  807. {
  808.     printf("    [POINTLIST 2\n\t[%lf %lf %lf]\n\t[%lf %lf %lf]\n    ]\n",
  809.        PEdge->Vertex[0]->Coord[0],
  810.        PEdge->Vertex[0]->Coord[1],
  811.        PEdge->Vertex[0]->Coord[2],
  812.        PEdge->Vertex[1]->Coord[0],
  813.        PEdge->Vertex[1]->Coord[1],
  814.        PEdge->Vertex[1]->Coord[2]);
  815.     printf("    [POLYLINE 2\n\t[%lf %lf %lf]\n\t[%lf %lf %lf]\n    ]\n",
  816.        PEdge->Vertex[0]->Coord[0],
  817.        PEdge->Vertex[0]->Coord[1],
  818.        PEdge->Vertex[0]->Coord[2],
  819.        PEdge->Vertex[1]->Coord[0],
  820.        PEdge->Vertex[1]->Coord[1],
  821.        PEdge->Vertex[1]->Coord[2]);
  822. }
  823.  
  824. #endif /* DEBUG1 */
  825.